package day_2022_9_to_12.Day;

import java.util.Arrays;

/**
 * @author haomin
 * @date 2022/09/15 14:48
 **/
public class Day13_2_Num416_canPartition {
    class Solution {
        boolean flag = false;
        public boolean canPartition(int[] nums){
            Arrays.sort(nums);
            int sum = 0;
            for(int i : nums) sum += i;
            dfs(nums, 0, nums.length-1, 0, sum);
            return flag;
        }
        private void dfs(int[] nums, int l, int r, int target, int sum){
            if(flag) return;
            if(target == (sum-target)) flag = true;
            for(int i = l; i < r; ++i){
                target += nums[i];
                dfs(nums, i+1, r, target, sum);
                target -= nums[i];
            }
        }
    }
}